package gold.enterprise;

public class ByteDanceTwo {

    class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public static ListNode sortList(ListNode head) {
        if (null == head || null == head.next) return head;

        // 查找链表中点,使用快慢指针
        ListNode fast = head, slow = head, middle = null;
        while (null != fast.next && null != fast.next.next) {
            slow = slow.next;
            fast = fast.next.next;
        }

        middle = slow.next;
        slow.next = null;

        ListNode leftHead = sortList(head);
        ListNode rightHead = sortList(middle);

        return mergeList(leftHead, rightHead);
    }

    /**
     * 双链表归并排序
     * 依旧是递归思路
     */
    public static ListNode mergeList(ListNode leftHead, ListNode rightHead) {
        if (null == leftHead) return rightHead;
        if (null == rightHead) return leftHead;

        if (leftHead.val < rightHead.val) {
            leftHead.next = mergeList(leftHead.next, rightHead);
            return leftHead;
        } else {
            rightHead.next = mergeList(leftHead, rightHead.next);
            return rightHead;
        }
    }

    public static void printList(ListNode head) {
        ListNode cur = head;

        while (null != cur) {
            System.out.print(cur.val + " -> ");
            cur = cur.next;
        }

        System.out.println("");
    }

    public void run() {
        ListNode head = new ListNode(3);
        ListNode t1 = new ListNode(2);
        ListNode t2 = new ListNode(1);
        ListNode t3 = new ListNode(-1);

        head.next = t1;
        t1.next = t2;
        t2.next = t3;

        printList(head);
        // 错误方式 sortList(head);
        head = sortList(head);//正确方式：head需要重新指向新头部
        printList(head);
    }

    public static void main(String[] args) {
        //Scanner in = new Scanner(System.in);
        //int a = in.nextInt();
        //System.out.println(a);

        ByteDanceTwo runner = new ByteDanceTwo();
        runner.run();

    }
}
